#include"main.h"

void create_tree(BiTreeNode** root_pp, char* pre_order_seq, int num_elements) {
	static int num_element = -1;
	num_element++;
	if (pre_order_seq[num_element] != '\0' && pre_order_seq[num_element] != '#') {
		(*root_pp) = (BiTreeNode*)malloc(sizeof(BiTreeNode));
		(*root_pp)->data = pre_order_seq[num_element];
		create_tree(&((*root_pp)->leftChild), pre_order_seq, num_elements);
		create_tree(&((*root_pp)->rightChild), pre_order_seq, num_elements);
	}
	else {
		(*root_pp) = 0;
	}
}

void pre_order_traverse(BiTreeNode* t, void visit(DataType item)) {
	if (t != 0) {
		visit(t->data);
		pre_order_traverse(t->leftChild, visit);
		pre_order_traverse(t->rightChild, visit);

	}
}

void in_order_traverse(BiTreeNode* t, void visit(DataType item)) {
	if (t != 0) {
		in_order_traverse(t->leftChild, visit);
		visit(t->data);
		in_order_traverse(t->rightChild, visit);
	}
}

void post_order_traverse(BiTreeNode* t, void visit(DataType item)) {
	if (t != 0) {
		post_order_traverse(t->leftChild, visit);
		post_order_traverse(t->rightChild, visit);
		visit(t->data);
	}
}

void visit(DataType item) {
	printf("%c\n", item);
}

BiTreeNode* search(BiTreeNode* root, DataType x) {
	if (root == 0) {
		return NULL;
	}
	else if ((root->data) == x) {
		return root;
	}
	BiTreeNode* a=search(root->leftChild, x);
	BiTreeNode* b=search(root->rightChild, x);
	if (a!=NULL){
		return a;
	}
	else {
		return b;
	}
}

void destroy(BiTreeNode** root) {
	if ((*root) != 0) {
		destroy(&((*root)->leftChild));
		destroy(&((*root)->rightChild));
		free(*root);
	}
}

int main() {
	void (*p)(DataType item) = visit;
	BiTreeNode* aa = 0;
	char po = 'A';
	create_tree(&aa, "ABC##DE#G##F###", 7);
	pre_order_traverse(aa, p);
	printf("%p", search(aa, po));
	destroy(&aa);
	return 0;
}